The present invention relates to a decoding device and a decoding method, and particularly to a decoding device and a decoding method that make it possible to decode a code resulting from encoding by a low density parity check code (LDPC code) with a high precision while preventing an increase in scale of the device.
Recently, researches in a field of communications such as mobile communications and deep space communications and in a field of broadcasting such as terrestrial broadcasting and satellite digital broadcasting, for example, have been advanced considerably. As such researches have been advanced, researches into coding theories have also been actively pursued for purposes of improvement in efficiency of error correction coding and decoding.
A so-called Shannon (C. E. Shannon) limit given by Shannon's channel coding theorem is known as a theoretical limit of code performance. Researches into coding theories are pursued with an objective of developing a code that offers performance close to the Shannon limit. Recently, methods referred to as turbo coding such as PCCCs (Parallel Concatenated Convolutional Codes) and SCCCs (Serially Concatenated Convolutional Codes), for example, have been developed as encoding methods that offer performance close to the Shannon limit. While these turbo codes have been developed, low density parity check codes (hereinafter referred to as LDPC codes) as an encoding method that has been known for a long time are drawing attention.
LDPC codes were first proposed by R. G. Gallager in “Low Density Parity Check Codes”, Cambridge, Mass.: M. I. T. Press, 1963. Thereafter LDPC codes were rediscovered in D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999, M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998, and the like.
Recent researches have found that, as with turbo codes and the like, LDPC codes offer performance that approaches the Shannon limit as code length is increased. Since LDPC codes have a characteristic in that minimum distance is in proportion to the code length, the LDPC code has advantages, as features thereof, of good block error probability characteristics and substantially no occurrence of a so-called error floor phenomenon, which is observed in characteristics of decoding of turbo codes and the like.
Such LDPC codes will be described concretely in the following. Incidentally, LDPC codes are linear codes, and are not necessarily binary codes; however, the following description will be made supposing that LDPC codes are binary codes.
LDPC codes have a principal characteristic in that a parity check matrix defining the LDPC codes is a sparse check matrix. A sparse matrix has a very small number of “1s” as components of the matrix. Supposing that a sparse check matrix is represented by H, such check matrices H include for example a check matrix H as shown in FIG. 1 in which the Hamming weight (the number of 1s) of each column is three and the Hamming weight of each row is six.
An LDPC code defined by such a check matrix H in which the Hamming weights of each row and each column are constant is referred to as a regular LDPC code. On the other hand, an LDPC code defined by a check matrix H in which the Hamming weights of each row and each column are not constant is referred to as an irregular LDPC code.
Encoding by such an LDPC code is implemented by generating a generator matrix G based on the check matrix H and multiplying the generator matrix G by a binary information message to generate a codeword. Specifically, an encoding device for performing encoding by an LDPC code first calculates a generator matrix G which satisfies an equation GHT=0 between a transposed matrix HT of the check matrix H and the generator matrix G. When the generator matrix G is a k×n matrix (a matrix of k rows and n columns), the check matrix H is a matrix of n−k rows and n columns.
The encoding device multiplies the generator matrix G by an information message (vector) u of k bits to generate a codeword (LDPC code) c (=uG) of n bits. The codeword c generated by the encoding device is mapped such that a code bit having a value “0” is converted into “+1” and a code bit having a value “1” is converted into “−1” for transmission. The transmitted codeword is received on a receiving side via a predetermined communication channel.
In a case where the codeword c of n bits is a systematic code that coincides with a bit string obtained by arranging n−k parity bits following the information message u of k bits, supposing that a part of n−k rows and k columns in the check matrix H of n−k rows and n columns which part corresponds to the information message u of k bits in the codeword c of n bits is referred to as an information part and that a part of n−k rows and n−k columns which part corresponds to n−k parity bits is referred to as a parity part, the information message u can be encoded into an LDPC code by using the check matrix H when the parity part forms a lower triangular matrix or an upper triangular matrix.
Specifically, for example, when the check matrix H is formed by the information part and the parity part of a lower triangular matrix as shown in FIG. 2, and elements in the lower triangular part of the parity part all have a value of one, a first bit of the parity bits of the codeword c has a value obtained by calculating an EXOR (exclusive disjunction) of bits of the information message u which bits correspond to elements having a value of one in a first row in the information part of the check matrix H.
A second bit of the parity bits of the codeword c has a value obtained by calculating an EXOR of bits of the information message u which bits correspond to elements having a value of one in a second row in the information part of the check matrix H and the first bit of the parity bits.
A third bit of the parity bits of the codeword c has a value obtained by calculating an EXOR of bits of the information message u which bits correspond to elements having a value of one in a third row in the information part of the check matrix H and the first and second bits of the parity bits.
Similarly, a subsequent ith bit of the parity bits of the codeword c has a value obtained by calculating an EXOR of bits of the information message u which bits correspond to elements having a value of one in an ith row in the information part of the check matrix H and the first to (i−1)th bits of the parity bits.
Thus, the codeword c of n bits can be obtained by determining the n−k parity bits and arranging the n−k parity bits following the information message u of k bits.
LDPC codes can be decoded by a probabilistic decoding algorithm proposed by Gallager, which is a message-passing algorithm based on belief propagation on a so-called Tanner graph including variable nodes (referred to also as message nodes) and check nodes. Variable nodes and check nodes will hereinafter be also referred to simply as nodes as appropriate.
In the probabilistic decoding, however, messages exchanged among nodes are real numbers, and it is therefore necessary to monitor the probability distribution itself of the messages assuming sequential numbers in order to analytically solve the messages. Thus, very difficult analysis is required. Therefore, Gallager has proposed algorithm A or algorithm B as an algorithm for decoding LDPC codes.
LDPC codes are generally decoded according to a procedure as represented in FIG. 3. In this case, suppose that an LDPC code (codeword c) received value is U0, that a message output from a check node (hereinafter referred to as a check node message as appropriate) is uj, and that a message output from a variable node (hereinafter referred to as a variable node message as appropriate) is vi. A message is a real number that expresses the likelihood of zero by a so-called log likelihood ratio. Further, the log likelihood ratio of the likelihood of zero of the received value U0 will be represented as received data u0i.
In the decoding of an LDPC code, as shown in FIG. 3, in first step S11, the received value U0 (received data u0i) is received, the message uj is initialized to “0”, and a variable k of an iterative processing counter which variable assumes an integer is initialized to “0”. The process proceeds to step S12. In step S12, the variable node message vi is obtained by performing an operation represented by Equation (1) on the basis of the received data u0i, and the check node message uj is obtained by performing an operation represented by Equation (2) on the basis of the variable node message vi.
                    [                  Equation          ⁢                                          ⁢          1                ]                                                                                      ⁢                              v            i                    =                                    u                              0                ⁢                i                                      +                                          ∑                                  j                  =                  1                                                                      d                    v                                    -                  1                                            ⁢                              u                j                                                                        (        1        )                                [                  Equation          ⁢                                          ⁢          2                ]                                                                                      ⁢                              tanh            ⁡                          (                                                u                  j                                2                            )                                =                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                                                  ⁢                          tanh              ⁡                              (                                                      v                    i                                    2                                )                                                                        (        2        )            
In Equations (1) and (2), dv and dc are arbitrarily selectable parameters representing the number of 1s in a vertical direction (row direction) and a horizontal direction (column direction), respectively, of the check matrix H. For example, in a case of a (3, 6) code, dv=3 and dc=6.
Incidentally, in the operation of Equation (1) or (2), a message input from an edge from which to output a message is not used as a product or sum operation parameter, and therefore a product or sum operation range is a range of one to dv−1 or one to dc−1. In practice, the operation represented by Equation (2) is performed by preparing in advance a table of a function R(v1, v2) represented by Equation (3), which is defined by one output with respect to two inputs v1 and v2, and sequentially (recursively) using the function R as shown in Equation (4).
[Equation 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)  (3)[Equation 4]uj=R(v1, R(v2, R(v3, . . . R(vdc−2, vdc−1))))  (4)
Further, in step S12, the variable k is incremented by one. The process proceeds to step S13. In step S13, whether the variable k is equal to or greater than predetermined iterative decoding times N is determined. When it is determined in step S13 that the variable k is not equal to or greater than N, the process returns to step S12 to thereafter repeat the same processing.
When it is determined in step S13 that the variable k is equal to or greater than N, the process proceeds to step S14, where a message v as a decoding result to be finally output is obtained by performing an operation represented by Equation (5), and the message v is output. Then the LDPC code decoding process is ended.
                    [                  Equation          ⁢                                          ⁢          5                ]                                                                                      ⁢                  v          =                                    u                              0                ⁢                i                                      +                                          ∑                                  j                  =                  1                                                  d                  v                                            ⁢                              u                j                                                                        (        5        )            
Unlike the operation of Equation (1), the operation of Equation (5) is performed using messages from all edges connected to the variable node.
In such decoding of an LDPC code, in the case of a (3, 6) code, for example, messages are exchanged between nodes as shown in FIG. 4. The operation represented by Equation (1) is performed at the nodes indicated by “=” (variable nodes) in FIG. 4, and the operation represented by Equation (2) is performed at the nodes indicated by “+” (check nodes). In particular, in the algorithm A, messages are binarized, and at a node indicated by “+”, an exclusive OR of dc−1 messages input to the node are calculated, and at a node indicated by “=”, when all of dv−1 messages input to the node have bit values different from the received data R (u0i), the code is inverted and then output.
On the other hand, researches into a method for implementing the decoding of LDPC codes have recently been pursued. Prior to the description of the implementing method, description will first be made of the decoding of an LDPC code in schematic form.
FIG. 5 shows an example of the parity check matrix of a (3, 6) LDPC code (an encoding rate of 1/2 and a code length of 12). The check matrix H of an LDPC code can be written by using a Tanner graph as in FIG. 6. In FIG. 6, a check node is denoted by “+”, and a variable node is denoted by “=”. A check node and a variable node correspond to a row and a column, respectively, of the check matrix H. A connection between a check node and a variable node is an edge, and corresponds to “1” in the check matrix. Specifically, when a component in a jth row and an ith column in the check matrix H is one, an ith variable node from the top (a “=” node) and a jth check node from the top (a “+” node) in FIG. 6 are connected to each other by an edge. The edge indicates that an LDPC code bit corresponding to the variable node has a constraint condition corresponding to the check node. Incidentally, FIG. 6 is a Tanner graph of the check matrix H of FIG. 5.
A sum-product algorithm as an LDPC code decoding method repeatedly performs a variable node operation and a check node operation.
The operation of Equation (1) is performed at a variable node as shown in FIG. 7. Specifically, in FIG. 7, a variable node message vi corresponding to an edge for which to calculate the variable node message vi is calculated using received information u0i and check node messages u1 and u2 from other edges connected to the variable node. Variable node messages corresponding to other edges are calculated in a similar manner.
Prior to the description of the check node operation, Equation (2) is rewritten as Equation (6) using the relation of an equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b), where sign(x) is 1 when x≧0, and is −1 when x<0.
                    [                  Equation          ⁢                                          ⁢          6                ]                                                                                                                                            ⁢                                                u                  j                                =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          (                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  tanh                          ⁡                                                      (                                                                                          v                                i                                                            2                                                        )                                                                                              )                                                                                                                                              =                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  sign                          ⁢                                                                                                          ⁢                                                      (                                                          tanh                              ⁢                                                                                                                          ⁢                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      sign                    ⁢                                                                                  ⁢                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
Further, when a nonlinear function φ(x) is defined as an equation φ(x)=ln(tan h(x/2)) (ln( ) is a natural logarithmic function) with x≧0, the inverse function φ−1(x) of the nonlinear function φ(x) is expressed by an equation φ−1(x)=2tan h−1(e−x). Therefore Equation (6) can be written as Equation (7).
                    [                  Equation          ⁢                                          ⁢          7                ]                                                                                      ⁢                              u            j                    =                                                    ϕ                                  -                  1                                            ⁡                              (                                                      ∑                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      ϕ                    ⁡                                          (                                                                                                v                          i                                                                                            )                                                                      )                                      ×                                          ∏                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                                                          ⁢                              sign                ⁢                                                                  ⁢                                  (                                      v                    i                                    )                                                                                        (        7        )            
The operation of Equation (7) is performed at a check node as shown in FIG. 8. Specifically, in FIG. 8, a check node message uj corresponding to an edge for which to calculate the check node message uj is calculated using variable messages v1, v2, v3, v4, and v5 from other edges connected to the check node. Check node messages corresponding to other edges are calculated in a similar manner.
Incidentally, the function φ(x) can also be expressed as φ(x)=ln((ex+1)/(ex−1)), and φ(x)=φ−1(x) when x>0. When the functions φ(x) and φ−1(x) are implemented in hardware, the functions φ(x) and φ−1(x) may be implemented by using a LUT (Look Up Table), and in such a case, an identical LUT is used for both of the functions φ(x) and φ−1(x).
The LDPC code decoding method is referred to not only as the sum-product algorithm but also as belief propagation, for example; however, operations performed in either case are the same.
An implementing method in a case of performing decoding by sequentially performing operations at nodes one by one (full serial decoding) will be described as an example of implementation of the sum-product algorithm in a decoding device.
Incidentally, when implementing the sum-product algorithm in hardware, it is necessary to perform the variable node operation represented by Equation (1) and the check node operation represented by Equation (7) repeatedly with an appropriate circuit scale and an appropriate operating frequency.
Suppose in this case that a code (an encoding rate of 2/3 and a code length of 108) represented by a check matrix H of 36 (rows)×108 (columns) in FIG. 9 is decoded, for example. The number of 1s in the check matrix H of FIG. 9 is 323, and therefore the number of edges in the Tanner graph is 323. In the check matrix of FIG. 9, zero is represented by “.”.
FIG. 10 shows an example of configuration of a decoding device that performs one-time decoding of an LDPC code.
The decoding device of FIG. 10 calculates a message corresponding to one edge for each clock for operation of the decoding device.
Specifically, the decoding device in FIG. 10 includes two edge memories 100 and 102, one check node calculator 101, one variable node calculator 103, one receiver memory 104, and one controlling unit 105.
In the decoding device of FIG. 10, messages are read from the edge memory 100 or 102 one by one, and a message corresponding to a desired edge is calculated using the messages. Messages obtained by the calculation are stored one by one in the edge memory 102 or 100 in a subsequent stage. Iterative decoding is achieved by serially connecting a plurality of decoding devices of FIG. 10 that perform the one-time decoding, or repeatedly using the decoding device of FIG. 10. Incidentally, suppose in this case that a plurality of decoding devices of FIG. 10 are connected to each other.
The edge memory 100 stores messages (variable node messages) D100 supplied from the variable node calculator 103 of a decoding device in a preceding stage (not shown) in order in which the check node calculator 101 reads the messages D100. Then, in a phase of check node calculation, the edge memory 100 supplies the check node calculator 101 with the messages D100 as messages D101 in the order in which the messages D100 are stored.
According to a control signal D106 supplied from the controlling unit 105, the check node calculator 101 performs an operation (check node operation) according to Equation (7) using the messages D101 (variable node messages vi) supplied from the edge memory 100. The check node calculator 101 supplies a message D102 (check node message uj) obtained by the operation to the edge memory 102 in a subsequent stage.
The edge memory 102 stores messages D102 supplied from the check node calculator 101 in a preceding stage in order in which the variable node calculator 103 in a subsequent stage reads the messages D102. Then, in a phase of variable node calculation, the edge memory 102 supplies the variable node calculator 103 with the messages D102 as messages D103 in the order in which the messages D102 are stored.
Further, the variable node calculator 103 is supplied with a control signal D107 from the controlling unit 105, and supplied with received data D104 from the receiver memory 104. According to the control signal D107, the variable node calculator 103 performs an operation (variable node operation) according to Equation (1) using the messages D103 (check node messages uj) supplied from the edge memory 102 and the received data D104 (received data u0i) supplied from the receiver memory 104. The variable node calculator 103 supplies a message D105 (variable node message vi) obtained as a result of the operation to the edge memory 100 of a decoding device in a subsequent stage not shown in the figure.
The receiver memory 104 stores the received data u0i of the LDPC code. The controlling unit 105 supplies the control signal D106 for controlling the check node operation and the control signal D107 for controlling the variable node operation to the check node calculator 101 and the variable node calculator 103, respectively. The controlling unit 105 supplies the control signal D106 to the check node calculator 101 when the messages of all edges are stored in the edge memory 100, and supplies the control signal D107 to the variable node calculator 103 when the messages of all edges are stored in the edge memory 102.
FIG. 11 shows an example of configuration of the check node calculator 101 in FIG. 10 that performs the check node operation on a one-by-one basis.
Incidentally, FIG. 11 shows the check node calculator 101 supposing that each message is quantized into a total of six bits including a sign bit (a bit representing a positive sign or a negative sign). That is, a message is represented by a six-bit quantization value assigned to each numerical value for uniformly dividing a predetermined numerical range into 64 values that can be represented by six bits including a sign bit.
In FIG. 11, the check node operation on the LDPC code represented by the check matrix H of FIG. 9 is performed. Further, the check node calculator 101 in FIG. 11 is supplied with a clock ck. The clock ck is supplied to necessary blocks. The blocks perform processing in synchronism with the clock ck.
According to a one-bit control signal D106, for example, supplied from the controlling unit 105, the check node calculator 101 in FIG. 11 performs the operation according to Equation (7) using the messages D101 (variable node messages vi) read one by one from the edge memory 100.
Specifically, a six-bit message D101 (variable node message vi) from a variable node corresponding to each column in the check matrix H is input one by one to the check node calculator 101. An absolute value D122 (|vi|), which is five less significant bits of the message D101, is supplied to a LUT 121, and a sign bit D121, which is the most significant bit of the message D101, is supplied to an EXOR circuit 129 and a FIFO (First In First Out) memory 133. The check node calculator 101 is also supplied with the control signal D106 from the controlling unit 105. The control signal D106 is supplied to a selector 124 and a selector 131.
The LUT 121 reads a five-bit operation result D123 (φ(|vi|)) obtained by performing the operation of the nonlinear function φ(|vi|) in Equation (7) in response to the absolute value D122 (|vi|). The LUT 121 supplies the five-bit result D123 (φ(|vi|)) to an arithmetic unit 122 and a FIFO memory 127.
The arithmetic unit 122 integrates the five-bit operation result D123 (φ(|vi|)) by adding the operation result D123 to a nine-bit value D124 stored in a register 123. The arithmetic unit 122 re-stores a resulting nine-bit integrated value in the register 123. Incidentally, when results D123 of operation on the absolute values D122 (|vi|) of messages D101 from all edges over one row of the check matrix H are integrated, the register 123 is reset.
The arithmetic unit 122 and the register 123 integrate the five-bit operation result D123 (φ(|vi|)) supplied from the LUT 121 a number of times that, at a maximum, corresponds to a maximum number of delays in the FIFO memory 127, that is, a maximum row weight of the check matrix H. The maximum row weight of the check matrix H in FIG. 9 is nine. Hence, the arithmetic unit 122 and the register 123 integrate the five-bit operation result D123 (φ(|vi|)) nine times at a maximum (perform integration for nine five-bit values). Thus, in order to be able to represent a value obtained by integrating the five-bit value nine times, the number of quantization bits in the output of the arithmetic unit 122 and subsequent outputs is nine, which is larger by four (a minimum number of bits that can represent nine (times)) than that of the five-bit operation result D123 (φ(|vi|)) output by the LUT 121.
When the messages D101 (variable node messages vi) over one row of the check matrix are read one by one, and an integrated value obtained by integrating operation results D123 for one row is stored in the register 123, the control signal D106 supplied from the controlling unit 105 is changed from zero to one. For example, in a case where the row weight of the check matrix is “9”, the control signal D106 is “0” for a first to an eighth clock, and is “1” for a ninth clock.
When the control signal D106 is “1”, the selector 124 selects the value stored in the register 123, that is, the nine-bit integrated value D124 (Σφ(|vi|) from i=1 to i=dc) obtained by integrating φ(|vi|) obtained from the messages D101 (variable node messages vi) from all the edges over one row of the check matrix H, and then outputs the value as a value D125 to the register 125 to store the value D125 in the register 125. The register 125 supplies the value D125 stored therein as a nine-bit value D126 to the selector 124 and an arithmetic unit 126. When the control signal D106 is “0”, the selector 124 selects the value D126 supplied from the register 125, and then outputs the value D126 to the register 125 to re-store the value D126 in the register 125. That is, until φ(|vi|) obtained from the messages D101 (variable node messages vi) from all the edges over one row of the check matrix H is integrated, the register 125 supplies previously integrated φ(|vi|) to the selector 124 and the arithmetic unit 126.
Meanwhile, the FIFO memory 127 delays the five-bit operation result D123 (φ(|vi|)) output by the LUT 121 until the new value D126 (Σφ(|vi|) from i=1 to i=dc) is output from the register 125, and then supplies the five-bit operation result D123 (φ(|vi|)) as a five-bit value D127 to the arithmetic unit 126. The arithmetic unit 126 subtracts the value D127 supplied from the FIFO memory 127 from the value D126 supplied from the register 125. The arithmetic unit 126 supplies a result of the subtraction as a five-bit subtraction value D128 to a LUT 128. That is, the arithmetic unit 126 subtracts φ(|vi|) obtained from a message D101 (variable node message vi) from an edge for which a check node message uj is desired to be obtained from the integrated value of φ(|vi|) obtained from the messages D101 (variable node messages vi) from all the edges over one row of the check matrix H. The arithmetic unit 126 supplies the subtraction value (Σφ(|vi|) from i=1 to i=dc−1) as the subtraction value D128 to the LUT 128.
Incidentally, since the arithmetic unit 126 subtracts the five-bit value D127 supplied from the FIFO memory 127 from the nine-bit value D126 supplied from the register 125, the result of the subtraction can be nine bits at a maximum, whereas the arithmetic unit 126 outputs the five-bit subtraction value D128. Therefore, when the result of the subtraction of the five-bit value D127 supplied from the FIFO memory 127 from the nine-bit value D126 supplied from the register 125 cannot be represented by five bits, that is, when the result of the subtraction exceeds a maximum value (31 (11111 as a binary number) that can be represented by five bits, the arithmetic unit 126 clips the result of the subtraction to the maximum value that can be represented by five bits, and then outputs the five-bit subtraction value D128.
The LUT 128 outputs a five-bit operation result D129 (φ−1(Σφ(|vi|))) obtained by performing the operation of the inverse function φ−1(Σφ(|vi|)) in Equation (7) in response to the subtraction value D128 (Σφ(|vi|) from i=1 to i=dc−1).
In parallel with the above processing, an EXOR circuit 129 calculates an exclusive OR of a one-bit value D131 stored in a register 130 and the sign bit D121, and thereby multiplies the sign bits together. The EXOR circuit 129 re-stores a one-bit multiplication result D130 in the register 130. Incidentally, when the sign bits D121 of messages D101 (variable node messages vi) from all edges over one row of the check matrix H are multiplied together, the register 130 is reset.
When a multiplication result D130 (Πsign(vi) from i=1 to dc) obtained by multiplying together the sign bits D121 of the messages D101 from all the edges over one row of the check matrix H is stored in the register 130, the control signal D106 supplied from the controlling unit 105 is changed from zero to one.
When the control signal D106 is “1”, the selector 131 selects the value stored in the register 130, that is, the value D131 (Πsign(vi) from i=1 to i=dc) obtained by multiplying together the sign bits D121 of the messages D101 from all the edges over one row of the check matrix H, and then outputs the value D131 as a one-bit value D132 to a register 132 to store the value D132 in the register 132. The register 132 supplies the value D132 stored therein as a one-bit value D133 to the selector 131 and an EXOR circuit 134. When the control signal D106 is “0”, the selector 131 selects the value D133 supplied from the register 132, and then outputs the value D133 to the register 132 to re-store the value D133 in the register 132. That is, until the sign bits D121 of the messages D101 (variable node messages vi) from all the edges over one row of the check matrix H are multiplied together, the register 132 supplies a previously stored value to the selector 131 and the EXOR circuit 134.
Meanwhile, the FIFO memory 133 delays the sign bit D121 until the new value D133 (Πsign(vi) from i=1 to i=dc) is output from the register 132 to the EXOR circuit 134, and then supplies the sign bit D121 as a one-bit value D134 to the EXOR circuit 134. The EXOR circuit 134 calculates an exclusive OR of the value D133 supplied from the register 132 and the value D134 supplied from the FIFO memory 133, and thereby divides the value D133 by the value D134. The EXOR circuit 134 then outputs a one-bit division result as a divided value D135. That is, the EXOR circuit 134 divides the value obtained by multiplying together the sign bits D121 (sign(|vi|) of the messages D101 from all the edges over one row of the check matrix H by a sign bit D121 (sign (vi)) of a message D101 from an edge for which a check node message uj is desired to be obtained. The EXOR circuit 134 supplies the divided value (Πsign(vi) from i=1 to i=dc−1) as the divided value D135.
The check node calculator 101 then outputs, as a message D102 (check node message uj), a total of six bits with the five-bit operation result D129 output from the LUT 128 as five less significant bits and the one-bit divided value D135 output from the EXOR circuit 134 as a most significant bit (sign bit).
As described above, the check node calculator 101 performs the operations of Equation (7), and thereby obtains the check node message uj.
Incidentally, since the maximum row weight of the check matrix H of FIG. 9 is nine, that is, since the maximum number of variable node messages vi supplied to the check node is nine, the check node calculator 101 has the FIFO memory 127 for delaying results (φ(|vi|)) of the operation of the nonlinear function on nine variable node messages vi and the FIFO memory 133. When a check node message uj for a row with a row weight of less than nine is to be calculated, an amount of delay in the FIFO memory 127 and the FIFO memory 133 is reduced to the value of the row weight.
FIG. 12 shows an example of configuration of the variable node calculator 103 in FIG. 10 that performs the variable node operation on a one-by-one basis.
Incidentally, as with FIG. 11, FIG. 12 shows the variable node calculator 103 supposing that each message is quantized into a total of six bits including a sign bit. Also in FIG. 12, the variable node operation on the LDPC code represented by the check matrix H of FIG. 9 is performed. The variable node calculator 103 in FIG. 12 is supplied with a clock ck. The clock ck is supplied to necessary blocks. The blocks perform processing in synchronism with the clock ck.
According to a one-bit control signal D107, for example, supplied from the controlling unit 105, the variable node calculator 103 in FIG. 12 performs the operation (variable node operation) according to Equation (1) using messages D103 read one by one from the edge memory 102 and received data D104 (u0i) read from the receiver memory 104.
Specifically, a six-bit message D103 (check node message uj) from a check node corresponding to each row in the check matrix H is input one by one to the variable node calculator 103. The message D103 is supplied to an arithmetic unit 151 and a FIFO memory 155. In addition, in the variable node calculator 103, six-bit received data D104 (u0i) read from the receiver memory 104 on a one-by-one basis is supplied to an arithmetic unit 156. Further, the variable node calculator 103 is supplied with the control signal D107 from the controlling unit 105. The control signal D107 is supplied to a selector 153.
The arithmetic unit 151 integrates the six-bit message D103 (check node message uj) by adding the six-bit message D103 to a nine-bit value D151 stored in a register 152. The arithmetic unit 151 re-stores a resulting nine-bit integrated value in the register 152. Incidentally, when messages D103 from all edges over one column of the check matrix H are integrated, the register 152 is reset.
The arithmetic unit 151 and the register 152 integrate the six-bit message D103 a number of times that, at a maximum, corresponds to a maximum number of delays in the FIFO memory 155, that is, a maximum column weight of the check matrix H. The maximum column weight of the check matrix H in FIG. 9 is five. Hence, the arithmetic unit 151 and the register 152 integrate the six-bit message D103 five times at a maximum (perform integration for five six-bit values). Thus, in order to be able to represent a value obtained by integrating the six-bit value five times, the number of quantization bits in the output of the arithmetic unit 151 and subsequent outputs is nine, which is larger by three (a minimum number of bits that can represent five [times]) than that of the six-bit message D103.
When the messages D103 over one column of the check matrix H are read one by one, and an integrated value obtained by integrating the message D103 for one column is stored in the register 152, the control signal D107 supplied from the controlling unit 105 is changed from zero to one. For example, in a case where the column weight of the check matrix is “5”, the control signal D107 is “0” for a first to a fourth clock, and is “1” for a fifth clock.
When the control signal D107 is “1”, the selector 153 selects the value stored in the register 152, that is, the nine-bit value D151 (Σuj from j=1 to dV) obtained by integrating the messages D103 (check node messages uj) from all the edges over one column of the check matrix H, and then outputs the value D151 to a register 154 to store the value D151 in the register 154. The register 154 supplies the value D151 stored therein as a nine-bit value D152 to the selector 153 and the arithmetic unit 156. When the control signal D107 is “0”, the selector 153 selects the value D152 supplied from the register 154, and then outputs the value D152 to the register 154 to re-store the value D152 in the register 154. That is, until the messages D103 (check node messages uj) from all the edges over one column of the check matrix H are integrated, the register 154 supplies a previously integrated value to the selector 153 and the arithmetic unit 156.
Meanwhile, the FIFO memory 155 delays the message D103 from the check node until the new value D152 (Σuj from j=1 to dV) is output from the register 154, and then supplies the message D103 as a six-bit value D153 to the arithmetic unit 156. The arithmetic unit 156 subtracts the value D153 supplied from the FIFO memory 155 from the value D152 supplied from the register 154. That is, the arithmetic unit 156 subtracts a check node message uj from an edge for which a variable node message vi is desired to be obtained from the integrated value of the messages D103 (check node messages uj) from all the edges over one column of the check matrix H. The arithmetic unit 156 thereby obtains the subtraction value (Σuj from j=1 to dV−1). Further, the arithmetic unit 156 adds the subtraction value (Σuj from j=1 to dV−1) to the received data D104 (u0i) supplied from the receiver memory 104. The arithmetic unit 156 supplies a resulting six-bit value as a message D105 (variable node message vi).
As described above, the variable node calculator 103 performs the operations of Equation (1), and thereby obtains the variable node message vi.
Incidentally, since the maximum column weight of the check matrix H of FIG. 9 is five, that is, since the maximum number of check node messages uj supplied to the variable node is five, the variable node calculator 103 has the FIFO memory 155 for delaying five check node messages uj. When a variable node message vi for a column with a column weight of less than five is to be calculated, an amount of delay in the FIFO memory 155 is reduced to the value of the column weight.
The arithmetic unit 156 performs the operations of subtracting the six-bit value D153 supplied from the FIFO memory 155 from the nine-bit value D152 supplied from the register 154, and adding the value obtained by the subtraction to the six-bit received data D104 supplied from the receiver memory 104. A result of the operations may be less than a minimum value that can be represented by the six-bit message D105, or may exceed a maximum value that can be represented by the six-bit message D105. When the operation result is less than the minimum value that can be represented by the six-bit message D105, the arithmetic unit 156 clips the operation result to the minimum value. When the operation result exceeds the maximum value that can be represented by the six-bit message D105, the arithmetic unit 156 clips the operation result to the maximum value.
In the decoding device of FIG. 10, the control signals are supplied from the controlling unit 105 according to the weights of the check matrix H. The decoding device of FIG. 10 can decode the LDPC codes of various check matrices H by changing only the control signals as long as the edge memories 100 and 102 and the FIFO memories 127, 133, and 155 in the check node calculator 101 and the variable node calculator 103 have sufficient capacities.
Though not shown in the figures, the decoding device of FIG. 10 performs the operation of Equation (5) in place of the variable node operation of Equation (1) in a final decoding stage, and outputs a result of the operation as a final decoding result.
When an LDPC code is decoded by using the decoding device of FIG. 10 repeatedly, the check node operation and the variable node operation are performed alternately. Specifically, in the decoding device of FIG. 10, the variable node calculator 103 performs the variable node operation using a result of the check node operation by the check node calculator 101, and the check node calculator 101 performs the check node operation using a result of the variable node operation by the variable node calculator 103.
Incidentally, while FIG. 10 shows a full serial decoding device that decodes an LDPC code by sequentially performing operations at nodes one by one as an example of implementation of a decoding device, other decoding devices have been proposed in C. Howland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes”, Symposium on Circuits and Systems, 2001 [Non-Patent Literature 1] and E. Yeo, P. Pakzad, B. Nikolic, and V. Anantharam, “VLSI Architectures for Iterative Decoders in Magnetic Recording Channels”, IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001 [Non-Patent Literature 2]. The Non-Patent Literature 1 is a full parallel decoding device that performs decoding by performing operations at all nodes simultaneously. The Non-Patent Literature 2 is a partly parallel decoding device that simultaneously performs operations at a certain number of nodes rather than one node or all nodes.
For example, in the decoding device of FIG. 10, the number of bits at least equal to a value obtained by multiplying the code length of the LDPC code by the number of bits of quantization values representing the received data D104 (the number of quantization bits) is required as a storage capacity of the receiver memory 104 for storing the received data D104. The number of bits at least equal to a value obtained by multiplying a total number of edges by the number of bits of quantization values representing messages is required as storage capacities of the edge memories 100 and 102 for storing the messages.
Hence, when the code length is 108, the number of bits of the quantization values representing the messages (including the received data D104) is six, and the number of edges is 323, as described above, the receiver memory 104 having a storage capacity of at least 648 (=108×6) bits and the edge memories 100 and 102 having a storage capacity of at least 1938 (=323×6) bits are required.
Incidentally, in this case, the code length is 108 for simplicity of the description; in practice, however, a few thousand is used as the code length of an LDPC code.
On the other hand, when considered simply, to improve accuracy of decoding of an LDPC code requires quantization values of a certain number of bits as the quantization values representing the messages (including the received data D104).
However, as described above, the storage capacities of the edge memories 100 and 102 and the receiver memory 104 are proportional to the number of bits of the quantization values representing the messages. Therefore, when the messages are represented by a quantization value of a large number of bits, high-capacity memories are required as memories forming the decoding device, thus increasing the scale of the device.